class Solution
{
public:
    int waysToReachTarget(int target, vector<vector<int>> &types)
    {
        int n = types.size();
        // dp[i][t]表示前i种type获得t分的全部方法数
        vector<vector<int>> dp(n, vector<int>(target + 1, 0));

        for (int count = 0; count <= types[0][0]; ++count)
        {
            int mark = count * types[0][1];
            if (mark <= target)
            {
                dp[0][mark] = 1;
            }
            else
            {
                break;
            }
        }

        for (int i = 1; i < n; ++i)
        {
            for (int t = 0; t <= target; ++t)
            {
                int mark = types[i][1];
                int count = types[i][0];
                for (int prevT = t; count >= 0 && prevT >= 0; prevT -= mark)
                {
                    dp[i][t] += dp[i - 1][prevT];
                    dp[i][t] %= 1'0000'0000'7;
                    --count;
                }
            }
        }

        return dp[n - 1][target];
    }
};